package com.Dec_Nine;

import java.util.Arrays;

import static java.lang.Integer.MAX_VALUE;

/**
 * 764. 最大加号标志
 * 在一个 n x n 的矩阵 grid 中，除了在数组 mines 中给出的元素为 0，其他每个元素都为 1。mines[i] = [xi, yi]表示 grid[xi][yi] == 0
 *
 * 返回  grid 中包含 1 的最大的 轴对齐 加号标志的阶数 。如果未找到加号标志，则返回 0 。
 *
 * 一个 k 阶由 1 组成的 “轴对称”加号标志 具有中心网格 grid[r][c] == 1 ，以及4个从中心向上、向下、向左、向右延伸，长度为 k-1，由 1 组成的臂。注意，只有加号标志的所有网格要求为 1 ，别的网格可能为 0 也可能为 1 。
 *
 *  
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/largest-plus-sign
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 *
 * 2022/11/09 23:47
 */

public class Solution764 {

    public int orderOfLargestPlusSign(int n, int[][] mines) {
        int[][] grid=new int[n][n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                grid[i][j]= MAX_VALUE;
            }
        }
        for (int[] mine:mines){
            int x=mine[0],y=mine[1];
            grid[x][y]=0;
        }
        for (int i = 0; i < n; i++) {
            int left=0,right=0,top=0,bottom=0;
            for (int j=0,k=n-1;j<n&&k>=0;j++,k--){
                left=grid[i][j]==0?0:left+1;
                right=grid[i][k]==0?0:right+1;
                top=grid[j][i]==0?0:top+1;
                bottom=grid[k][i]==0?0:bottom+1;


                grid[i][j]=Math.min(left,grid[i][j]);
                grid[j][i]=Math.min(top,grid[j][i]);
                grid[i][k]=Math.min(right,grid[i][k]);
                grid[k][i]=Math.min(bottom,grid[k][i]);
            }
        }
        int res=0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                res=Math.max(res,grid[i][j]);
            }
        }
        return res;
    }

    public static void main(String[] args) {
        Solution764 solution764=new Solution764();
        System.out.println(solution764.orderOfLargestPlusSign(5,new int[][]{{4,2}}));
    }

}
